Аутобуске руте
| време | меморија | улаз | излаз |
|---|---|---|---|
| 0,5 s | 64 Mb | стандардни излаз | стандардни улаз |
Познате су руте аутобуса у једном граду. Напиши програм који одређује најмањи број вожњи аутобусом потребан да се стигне од дате почетне до дате завршне станице.
Улаз
Са стандардног улаза се уноси број аутобуса \(n\) (\(1 \leq n \leq 10^5\)). Наредних \(n\) редова описује руте тих \(n\) аутобуса. За сваку руту је наведен број \(m\) (\(1 \leq m \leq 10^5\)) станица дуж те руте, а затим и \(m\) различитих редних бројева који представљају станице дуж руте. Аутобуси дуж руте пролазе у оба смера. Укупан број различитих станица на свим рутама није већи од \(10^5\), а укупан збир бројева свих станица на свим рутама није већи од \(5\cdot 10^6\). У последњем реду се налазе редни бројеви две станице – почетне и крајње.
Излаз
На стандардни излаз исписати минимални број вожњи потребан да се стигне са почетне до крајње станице. Ако није могуће стићи, исписати -1.
Пример
Улаз
2 3 1 2 7 3 3 6 7 1 6
Излаз
2
Објашњење
Најбоље је на станици 1 се укрцати на први аутобус, ићи до станице 7 и тамо прећи на други аутобус који ће нас одвести до станице 6.
Морате бити улоговани како бисте послали задатак на евалуацију.